package william.greedy;

/**
 * @author ZhangShenao
 * @date 2024/3/26
 * @description <a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode121_买卖股票的最佳时机 {
    /**
     * 采用动态规划算法
     * 记录两个值:最低股价minPrice和最大利润maxProfit
     * 遍历数组,判断当天是否可以以更低价格买入,同时判断如果当天卖出是否可以获得更大利润,同时更新minPrice和maxProfit
     * <p>
     * 时间复杂度O(N) 仅遍历一次数组
     * 空间复杂度O(1)
     */
    public int maxProfit(int[] prices) {
        //边界条件校验
        if (prices == null || prices.length < 1) {
            return 0;
        }

        //记录最低股价minPrice和最大利润maxProfit
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        //遍历数组
        for (int i = 0; i < prices.length; i++) {
            //判断当天是否可以以更低价格买入,同时判断如果当天卖出是否可以获得更大利润
            //同时更新minPrice和maxProfit
            minPrice = Math.min(minPrice, prices[i]);

            maxProfit = Math.max(maxProfit, (prices[i] - minPrice));
        }

        //返回最大利润
        return maxProfit;
    }
}
